1. Technical Field
The invention is related to character segmentation performed in an optical character recognition system prior to character identification, and in particular to character segmentation employing an associative memory or neural network.
2. Background Art
The problem in optical character recognition of segmenting individual character images from one another in a bit-map image of a document prior to identifying the individual character images is well-known. In many cases, adjacent individual characters may actually appear to be joined, either because of overlapping or kerning or because of noise in the image. Character segmentation is an essential preparatory step for character identification to be carried out reliably.
While many techniques have been proposed for performing character segmentation, they are for the most part very complex. It would be a great advantage if one could simply step a movable window of a size corresponding to an individual character across a document image pixel-by-pixel and reliably determine for each position of the window whether or not it has captured an individual character. If so, the image captured within the window would be transmitted to a down-stream character identification device. Otherwise, the captured image would not be transmitted. Such a procedure would enjoy the significant advantage of simplicity. However, no way of implementing such a procedure reliably has been found.
For example, U.S. Pat. No. 4,932,065 to Feldgajer describes a technique (illustrated in FIGS. 1a and 1b herein) for segmenting characters 10, 12 (FIG. 1a) for optical character recognition using a movable examining window 14 (FIG. 1b) corresponding in size to a single character, and moving the window pixel-by-pixel through the entire bit-map image 16 of the document. At each step, the image captured inside the window 14 is processed to determine whether the image within the window corresponds to an individual character. However, the processing employed is not sufficiently reliable. Specifically, the contents of the image captured within the window 14 at each position thereof is multiplied pixel-by-pixel with respective elements of a kernel 18 identical in size to the movable window 14, and the sum of all products is used as a "score" to determine whether the current window position is centered on one of the known characters. The elements of the kernel 18 correspond to a probability for each pixel in the window whether that pixel is "on" whenever the window is centered over any one of the characters in a known character set. Thus, each kernel element is a probability density function across all characters in the known character set. The magnitude of the kernel elements or individual probability density functions is indicated within the kernel 18 of FIG. 1a by tone, the darker areas of the kernel 18 containing elements or probability density functions of higher amplitude. The kernel 18 is produced in a straightforward manner by totalling for each pixel in the movable window the number of times it is "on" as each character in the known character set is centered in the movable window, as depicted in FIG. 1a.
Such a technique is not reliable: The computation of the score is not particularly immune to "false" high scores attributable to portions of adjacent characters simultaneously captured within the window when the window is NOT centered over one individual character. Depending upon the character font, such a non-character captured image (i.e., an image straddling two adjacent characters) frequently may have a high correlation to many of the large amplitude elements in the mask of probability density functions, and thus produce a false "high" score, leading the system to the incorrect conclusion that the captured image is that of an individual character.
Depending upon its frequency of occurrence, such an error is unacceptable in commercially marketed optical character recognition systems. Thus, it has not seemed possible to reliably perform character segmentation by simply stepping an intelligent window or kernel across the bit-map image of a document. Accordingly, the art must currently turn to far more complex techniques for reliable character segmentation, a significant burden.
Therefore, it is an object of the present invention to provide a reliable process for segmenting characters by stepping a window or intelligent kernel pixel-by-pixel across the bit-map image of a document, thereby achieving simplicity without sacrificing reliability.
It is a further object of the invention to provide such a process with a strong immunity against falsely identifying portions of adjacent characters captured within the window at a given position as an individual character.